/* 
    在有序数组中查找是否有某个值。 时间复杂度：O(log~2~N)，因为最差：2^n^=N
*/
let dichotomy = function (arr, search) {
    let low = 0
    let high = arr.length - 1
    while (high >= low) {
        let mid = Math.floor((high + low) / 2)
        if (arr[mid] === search) {
            return mid
        } else if (arr[mid] > search) {
            high = mid - 1
        } else if (arr[mid] < search) {
            low = mid + 1
        }
    }
    return -1
}

let arr = [1, 2, 38, 93, 111, 125, 8989, 89898]
console.log(dichotomy(arr, 8989))
